﻿#include <iostream>
#include <unordered_map>

using namespace std;

#define MAX(a, b) (a > b ? a : b)

/**
 * 暴力递归方法，以index结尾，最长子数组长度是多少
 */
static int recur(const int* numbers, const size_t numberCount, const int k, const int index)
{
    if (index == 0)
    {
        if (numbers[index] == k) return 1;
        return 0;
    }

    int sum = 0;
    int finalIndex = index;
    for (int i = index; i >= 0; i--)
    {
        sum += numbers[i];
        if (sum == k)
            finalIndex = i;
    }

    int count = index - finalIndex + 1;
    int prev = recur(numbers, numberCount, k, index - 1);
    return MAX(count, prev);
}

/**
 * 使用前缀和，将位置i和之前的所有的前缀和都记录到map中，然后看是否存在一个前缀和，使得这个前缀和+k=当前的总和
 */
static int byPrefixSum(const int* numbers, const size_t numberCount, const int k)
{
    unordered_map<int, int> prefixSum2IndexMap;
    int longestLength = 0;
    int sum = 0;
    int prefix;
    int prefixIndex;
    for (int i = 0; i < numberCount; i++)
    {
        sum += numbers[i];
        if (sum == k)
        {
            longestLength = MAX(longestLength, i + 1);
        }

        if (!prefixSum2IndexMap.count(sum))
        {
            prefixSum2IndexMap[sum] = i;
        }

        prefix = sum - k;
        if (prefixSum2IndexMap.count(prefix))
        {
            prefixIndex = prefixSum2IndexMap[prefix];
            longestLength = MAX(longestLength, i - prefixIndex);
        }
    }

    return longestLength;
}

/**
 * 求一个无序整数数组(有正，有负，有零)的所有子数组中所有元素相加和等于k的最长子数组长度
 */
int main_sumOfTheLongestIntegerSubarrayEqualToK()
{
    int numbers[] = { 1,3,-3,6,5,-8,0,10,-4,-6,-5,-3 };
    int count = sizeof(numbers) / sizeof(int);
    int k = 3;

    int longestSubarrayLength = 0;
    int curSubarrayLength;
    for (int i = 0; i < count; i++)
    {
        curSubarrayLength = recur(numbers, count, k, i);
        longestSubarrayLength = MAX(longestSubarrayLength, curSubarrayLength);
    }

    printf("max length by recur:%d\n", longestSubarrayLength);

    longestSubarrayLength = byPrefixSum(numbers, count, k);
    printf("max length by prefix sum:%d\n", longestSubarrayLength);

    return 0;
}